package com.demo.贪心算法;

import cn.hutool.core.lang.Console;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

/**
 * 金条切割
 * 如何切割花费最少
 * @author cl
 */
public class GoldBarSlicing {

    public static void main(String[] args) {
        List<Integer> ret = slicing(Arrays.asList(10, 20, 30));
        Console.log("花费最少为：{}，切割步骤是：{}", ret.stream().mapToInt(Integer::valueOf).sum(), Arrays.toString(ret.toArray()));
    }

    public static List<Integer> slicing(List<Integer> blocks) {
        List<Integer> result = new ArrayList<>();
        PriorityQueue<Integer> heap = new PriorityQueue<>(blocks);
        while (heap.size() > 1) {
            Integer a = heap.poll();
            Integer b = heap.poll();
            Integer sum = a + b;
            result.add(sum);
            heap.add(sum);
        }
        return result;
    }
}
